package parallel.project.graph;

import java.awt.Point;
import java.io.IOException;
import java.io.Serializable;
import java.lang.invoke.CallSite;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

import parallel.project.framework.Serializer;
import parallel.project.graph.Edge;

/**
 * Defines a path across a {@link Graph}, composed of {@link Edge}s,
 * Each {@link Edge} is directed in the direction of the path traversal
 * and thus each {@link Edge} ends where the next begins.
 * 
 * @author Adam Clayton
 * @author Larry Walters
 */
@SuppressWarnings("serial")
public class Path implements Serializable 
{
	/**
	 * The list of {@link Edge}s that form the path, where the
	 * {@link Edge} at index i comes right before the one at index i+1.
	 * This means that the {@link Edge} at index i should end at the
	 * same {@link Node} that the {@link Edge} at index i+1 starts at.
	 */
	private List<Edge> edges;
	
	/** Starting {@link Node} */
	private Node start;
	
	/** Ending {@link Node} */
	private Node end;
	
	/**
	 * Creates an empty path
	 */
	public Path() 
	{
		this.edges = new ArrayList<Edge>();
	}
	
	/**
	 * Creates a path with the given {@link List} or {@link Edge}s.
	 * Since just making this list the path, there is no check on the
	 * ordering, and it may be from an undirected path, so must specify
	 * the starting and stopping locations.
	 * 
	 * @param edgeList
	 * 		{@link Edge}s to assign to this path
	 * @param start
	 * 		Start point
	 * @param end
	 * 		End point
	 */
	public Path(List<Edge> edgeList, Node start, Node end)
	{
		this.edges = edgeList;
		this.start = start;
		this.end = end;
	}
	
	/**
	 * Adds the given {@link Edge} at the end of the path.  Throws an
	 * exception if the ending {@link Node} of the current ending edge
	 * is not the same as the starting {@link Node} of this 
	 * {@link Edge}.
	 * 
	 * @param edge
	 * 		The {@link Edge} to add at the end of the path.  The
	 * 		{@link Edge} is considered directional; the path proceeds
	 * 		from the first {@link Node} (returned with
	 * 		{@link Edge.getFirst()}) to the second {@link Node} 
	 * 		(returned with {@link Edge.getSecond()}).
	 */
	public void addEdge(Edge edge) throws GraphException
	{
		// current last edge
		if (this.edges.size() == 0)
		{
			this.edges.add(edge);
			this.start = edge.getFirst();
			this.end = edge.getSecond();
		}
		else
		{
			Edge last = this.edges.get(this.edges.size() - 1);
			// check that the first node in the given edge is the second 
			// node in the last edge; if it isn't, throw an exception
			if (last.getSecond().equals(edge.getFirst()))
				this.edges.add(edge);
			else
			{
				throw new GraphException("Given edge does not start " +
					"at the current last node (" + 
					last.getSecond().getName() + 
					") of the path (it starts at " + 
					edge.getFirst().getName() + ")");
			}
			this.end = edge.getSecond();
		}
	}

	/**
	 * Tests if the path contains the given {@link Edge}
	 * 
	 * @param edge
	 * 		The {@link Edge} to test for containment
	 * 
	 * @return
	 * 		True if the {@link Edge} is part of this path, false if not
	 */
	public boolean containsEdge(Edge edge)
	{
		return this.edges.contains(edge);
	}
	
	/**
	 * Tests if the given point is in this path; that is, is it the
	 * location of any of the {@link Node}s or on one of the 
	 * {@link Edge}s.
	 * 
	 * @param loc
	 * 		The point to test if it is in the path
	 * 
	 * @return
	 * 		True if it is in the path, false if not
	 */
	public boolean containsPoint(Point loc)
	{
		for (Edge edge : this.edges)
		{
			if (edge.getLocations().contains(loc) ||
				edge.getFirst().getLocation().equals(loc) ||
				edge.getSecond().getLocation().equals(loc))
				return true;
		}
		// if get here, then didn't find the point in any edge's
		// location list nor was it the location of any node in the path
		return false;
	}
	
	/**
	 * Returns a read-only version of all the {@link Edge}s in this 
	 * path.  Note that this also orders the locations in the 
	 * {@link Edge}s before returning them.
	 * 
	 * @return
	 * 		All {@link Edge}s in this path, read-only
	 */
	public List<Edge> getAllEdges()
	{
		this.orderLocations();
		return Collections.unmodifiableList(this.edges);
	}
	
	/**
	 * Returns all the {@link Node}s in the path, in the order they
	 * occur, starting at 0th index.  It is read-only.  Note that this
	 * just calls {@link #orderLocations()} which means the 
	 * {@link Edge}s get ordered as well.
	 * 
	 * @return
	 * 		All {@link Nodes} in the path
	 */
	public List<Node> getAllNodes()
	{
		return this.orderLocations();
//		List<Node> nodes = new ArrayList<Node>();
//		// go through the list of edges and for each try to add both
//		// nodes, if they haven't already been added, which will fail a
//		// lot of the time, but this way ensures that all the nodes are
//		// included, since don't know when to add the first of the
//		// second
//		for (Edge edge : this.edges)
//		{
//			if (!nodes.contains(edge.getFirst()))
//				nodes.add(edge.getFirst());
//			if (!nodes.contains(edge.getSecond()))
//				nodes.add(edge.getSecond());
//		}
//		// return all the nodes
//		return Collections.unmodifiableList(nodes);
	}
	
	public List<Point> getAllPoints()
	{
		List<Point> points = new ArrayList<Point>();
		List<Edge> edgeList = this.getAllEdges();
		// for each edge, add the point for both nodes, only if they are
		// not already in the list, and all the edge points; assume
		// that the points in the edges are ordered, which they should
		// be from getAllEdges
		for (Edge edge : edgeList)
		{
			Point firstLoc = edge.getFirst().getLocation();
			Point secondLoc = edge.getSecond().getLocation();
			// point for testing if the first node is contiguous to it,
			// which will determine if the first node or second should
			// be added next
			Point testPoint;
			// if there are points in the list, use the last one
			if (points.size() > 0)
				testPoint = points.get(points.size() - 1);
			// otherwise, just add the first node location and edge
			// locations and skip the rest of loop
			else
			{
				points.add(this.start.getLocation());
				points.addAll(edge.getLocations());
				continue;
			}
//			// if there are no points in the edge
//			if (edge.getLocations().size() == 0)
//			{
//				// if there are points in the list, use the last one
//				if (points.size() > 0)
//					testPoint = points.get(points.size() - 1);
//				// otherwise, have to use the first in the path
//				else
//					testPoint = this.start.getLocation();
//			}
//			// otherwise, use the first point in the edge
//			else
//				testPoint = edge.getLocations().get(0);
			// true if the first node is the next one in the path
			boolean firstNext = this.isContiguous(testPoint,firstLoc);
			// if the first next one in the path, add it, only if it
			// is not already in the list
			if (firstNext)
			{
				if (!points.contains(firstLoc))
					points.add(firstLoc);
			}
			// otherwise add the second one, since it is the next, but
			// only if it is not already in the path
			else
			{
				if (!points.contains(secondLoc))
					points.add(secondLoc);
			}
			// now add all the in order edge points
			points.addAll(edge.getLocations());
		}
		// add the last point
		points.add(this.end.getLocation());
		return points;
	}	
	
	/**
	 * Returns the ending {@link Node} of this {@link Path}, or null if
	 * this is an empty path.
	 * 
	 * @return
	 * 		End of this path
	 */
	public Node getEnd()
	{
		return this.end;
	}
	
	/**
	 * Returns the starting {@link Node} of this {@link Path}, or null
	 * if this is an empty path.
	 * 
	 * @return
	 * 		Start of this path
	 */
	public Node getStart()
	{
		return this.start;
	}
	
	/**
	 * Tests if the two points are right next to each other in the
	 * cardinal directions up, down, left, right.
	 * 
	 * @param one
	 * 		First point
	 * @param two
	 * 		Second point
	 * 
	 * @return
	 * 		True if the points border each other in one of the four
	 * 		cardinal directions, false if not
	 */
	private boolean isContiguous(Point one, Point two)
	{
		if (Math.abs(two.x - one.x) == 1 && one.y == two.y)
			return true;
		else if (Math.abs(two.y - one.y) == 1 && one.x == two.x)
			return true;
		else
			return false;
	}
	
	/**
	 * Returns a list of the {@link Node}s in this path in the order
	 * that they are encountered from start to end (0th indexed node is
	 * the first, 1st indexed is the second, etc., with the last index
	 * being the end).  It also orders the locations of the points on
	 * the {@link Edge}s so that they are ordered from the beginning
	 * {@link Node} for that {@link Edge}, in terms of path order, to
	 * the ending node (so the 0th indexed point is contiguous to the
	 * beginning {@link Node} and the last indexed point is contiguous
	 * to the ending {@link Node} for that {@link Edge}.
	 * 
	 * @return
	 * 		Nodes in this path ordered from start to end, read-only
	 */
	public List<Node> orderLocations()
	{
//		System.out.println("ordering locations ---->");
		// list of the nodes in order of the path (first at 0th index,
		// last at end index)
		List<Node> nodeOrdered = new ArrayList<Node>();
		// current node the point locations should start out contiguous
		// to (0th index in point list is contiguous to this node)
		Node current = this.start;
		// go through the edges, and flip the list of locations when
		// necessary
		for (Edge edge : this.edges)
		{
//			System.out.println("current = " + current.getLocation().toString());
			// add the current node to the order
			nodeOrdered.add(current);
			List<Point> locs = edge.getLocations();
			// only do something if the list is non-empty
			if (!locs.isEmpty())
			{
//				System.out.println("Testing against " + locs.get(locs.size() - 1).toString());
				// if the current node is contiguous with the location 
				// at the end of the edge point list, then the point 
				// list should be flipped
				boolean flipList = this.isContiguous(
					locs.get(locs.size() - 1),current.getLocation());
				if (flipList)
				{
//					System.out.println("do flip");
					edge.reverseLocations();
//					System.out.println("now first is " + edge.getLocations().get(0).toString());
				}
			}
			// get the next node, which is the other one in the edge
			current = edge.getOtherNode(current);
		}
//		System.out.println("current at end = " + current.getLocation().toString());
		// add the last node to the ordered list
		nodeOrdered.add(current);
		return Collections.unmodifiableList(nodeOrdered);
	}
	
	/**
	 * Prints a textual version of this path (with all the {@link Node}
	 * locations and {@link Edge} locations inbetween) to standard out. 
	 */
	public void printPath()
	{
		System.out.println("Start : " + 
			this.getStart().getLocation().toString());
		// go through the edges and print out the locations of each
		// edge and node's between them
		for (int i = 0; i < this.edges.size(); i++)
		{
			Edge edge = this.edges.get(i);
			System.out.println("Edge : " +
				edge.getFirst().getLocation().toString() + " -- " +
				edge.getSecond().getLocation().toString());
			/*if (i != 0)
			{
				System.out.println("Node : " + 
					edge.getFirst().getLocation().toString());
			}*/
			for (int j = 0; j < edge.getLocations().size(); j++)
			{
				Point point = edge.getLocations().get(j);
				System.out.println("\t" + point.toString());
			}
		}
		System.out.println("End : " + 
			this.getEnd().getLocation().toString());
	}
	
	/**
	 * Reads from the given file and returns the {@link Path} object
	 * read.  The file should only contain a single {@link Path} object
	 * written using <code>writePath</code>.  This uses basic Java
	 * serialization.
	 * 
	 * @param filename
	 * 		The name of the file to read the {@link Path} from
	 * 
	 * @return
	 * 		The {@link Path} object read from the file
	 * @throws ClassNotFoundException
	 * @throws IOException
	 */
	public static Path readPath(String filename) 
		throws ClassCastException,ClassNotFoundException,IOException
	{
		return Serializer.readObject(new Path(),filename);
	}
	
	/**
	 * Writes this {@link Path} to the file with the given filename.  
	 * This should be the only thing written to this file, if you 
	 * intend to retrieve the contents at some other time with a call 
	 * to <code>readPath</code>.  This uses basic Java serialization.
	 * 
	 * @param filename
	 * 		The name of the file to write to
	 * @throws IOException
	 */
	public void writePath(String filename) throws IOException
	{
		Serializer.writeObject(this,filename);
	}
}
